/*
 * One_Tree.c
 *
 *  Created on: 24/apr/2013
 *      AAuthors: Ialenti Andrea, Marangon Fabio
 */
#include "../headers/StatusCodes.h"
#include "../headers/OneTree.h"
#include "../headers/Utility.h"

Status findMinCostEdges(const Config *cfg, const Graph *g, int *idx1, int *idx2) {
	int i;
	double min1, min2, tmp;

	//	Find the 2 edges with the minimum costs.
	min1 = min2 = cfg->INF;
	for (i = 1; i < g->size; i++) {
		tmp = g->edges[0][i].cost;
		if(tmp > cfg->EPS || tmp < -cfg->EPS){
			if (tmp < min1) {
				min2 = min1;
				min1 = tmp;
				*idx2 = *idx1;
				*idx1 = i;
			} else if (tmp < min2) {
				min2 = tmp;
				*idx2 = i;
			}
		}
	}

	//	Check if the chosen edges are edges that were denied (branch and bound only).
	if(min1 < cfg->INF && min2 < cfg->INF)
		return SUCCESS;
	else
		return ERR_BB_GENERIC;
}

Status PrimDijkstra(const Config *cfg, const Graph *g, OneTree *t) {

	//	Copy the first node from the graph into the MST (node '0' is excluded).
	cpNode(&g->nodes[1], &t->nodes[1]);

	//	Variables used by the Prim-Dijkstra algorithm.
	int i, j;
	double min = g->max;
	int h = 0;
	double *L = initDblArray(g->size);
	int *flag = initIntArray(g->size);
	int *pred = initIntArray(g->size);

	//	Algorithm initialization.
	flag[1] = 1;
	pred[1] = 1;
	for (i = 2; i < g->size; i++) {
		flag[i] = 0;
		if((g->edges[1][i].cost > -cfg->EPS && g->edges[1][i].cost < cfg->EPS))
			L[i] = cfg->INF;
		else
			L[i] = g->edges[1][i].cost;
		pred[i] = 1;
	}

	//	Compute the MST.
	for (j = 1; j < g->size - 1; j++, min = cfg->INF) {
		for (i = 2; i < g->size; i++)
			if (flag[i] == 0 && L[i] < min) {
				min = L[i];
				h = i;
			}
		flag[h] = 1;
		for (i = 2; i < g->size; i++)
			if (flag[i] == 0 && g->edges[h][i].cost < L[i] && !(g->edges[h][i].cost > -cfg->EPS && g->edges[h][i].cost < cfg->EPS)) {
				L[i] = g->edges[h][i].cost;
				pred[i] = h;
			}
	}

	//	Build the tree 't'.
	resetCosts(t);

	//	Copy the nodes.
	for (i = 2; i < t->size; i++)
		cpNode(&g->nodes[i], &t->nodes[i]);

	for (i = 1; i < t->size; i++) {

		//	Check that no 0-cost edge nor denied edge are chosen.
		if ((g->edges[i][pred[i]].cost == 0 || g->edges[i][pred[i]].cost == cfg->INF) && pred[i] != i) {
			freeDblArray(L);
			freeIntArray(flag);
			freeIntArray(pred);
			return ERR_BB_GENERIC;
		}

		//	Update the cost matrix.
		t->costs[i][pred[i]] = t->costs[pred[i]][i] = g->edges[i][pred[i]].cost;

		//	Update the total cost of the tree.
		t->tc += g->costs_origin[i][pred[i]];

		t->edges[i].start = &t->nodes[pred[i]];
		t->edges[i].end = &t->nodes[i];
		t->edges[i].cost = g->edges[pred[i]][i].cost;

		t->edges[i].prev = &t->edges[pred[i]];

		t->totalCost += t->edges[i].cost;
	}

	//	Free memory.
	freeDblArray(L);
	freeIntArray(flag);
	freeIntArray(pred);
	return SUCCESS;
}

Status computeOneTree(const Config *cfg, const Graph *g, OneTree *t) {
	int i, j;

	//	Reset 1-tree costs.
	resetCosts(t);

	//	Calculate the 1-tree.
	Status status;
	status = findMinCostEdges(cfg, g, &i, &j);
	if(status != SUCCESS)
		return status;

	status = PrimDijkstra(cfg, g, t);
	if(status != SUCCESS)
		return status;

	//	Save the two min-cost indices.
	t->i1 = i;
	t->i2 = j;

	//	Set the edges 'e0' and 'e1'.
	t->edges[0].start = &t->nodes[0];
	t->edges[1].start = &t->nodes[0];
	t->edges[0].end = &t->nodes[t->i1];
	t->edges[1].end = &t->nodes[t->i2];
	t->edges[0].cost = g->edges[0][t->i1].cost;
	t->edges[1].cost = g->edges[0][t->i2].cost;

	//	Update the 1-tree cost matrix.
	cpNode(&g->nodes[0], &t->nodes[0]);
	t->costs[0][t->i1] = t->costs[t->i1][0] = g->edges[0][t->i1].cost;
	t->costs[0][t->i2] = t->costs[t->i2][0] = g->edges[0][t->i2].cost;

	t->tc += g->costs_origin[0][t->i2] + g->costs_origin[0][t->i1];
	t->totalCost += t->edges[0].cost + t->edges[1].cost;

	//	Calculate nodes degree and the number of forced edges for each node (used only in the branch and bound).
	for (i = 0; i < t->size; i++) {
		t->nodes[i].degree = 0;
		t->nodes[i].forced = 0;

		for (j = 0; j < t->size; j++) {
			if (!(t->costs[i][j] > -cfg->EPS && t->costs[i][j] < cfg->EPS) && i != j)
				t->nodes[i].degree++;
			if ((t->costs[i][j] > -cfg->INF - cfg->EPS && t->costs[i][j] < -cfg->INF + cfg->EPS) && i != j)
				t->nodes[i].forced++;
		}
	}
	return SUCCESS;
}

bool checkTour(const OneTree *t) {
	int i = 0;

	//	Check that every node has exactly 2 edges.
	while (t->nodes[i].degree == 2 && i < t->size)
		i++;

	return (i == t->size) ? true : false;
}

Status resetCosts(OneTree *t) {
	int i, j;

	t->totalCost = 0;
	t->tc = 0;
	for (i = 0; i < t->size; i++) {
		t->edges[i].cost = 0;
		for (j = 0; j < t->size; j++)
			t->costs[i][j] = t->costs[j][i] = 0;
	}
	return SUCCESS;
}

Status cpTree(const OneTree *src, OneTree *dest) {
	int i, j;

	dest->size = src->size;
	dest->tc = src->tc;
	dest->totalCost = src->totalCost;
	dest->v0 = src->v0;
	dest->i1 = src->i1;
	dest->i2 = src->i2;

	//	Deep copy the nodes.
	for (i = 0; i < src->size; i++)
		cpNode(&src->nodes[i], &dest->nodes[i]);

	//	Deep copy the edges.
	for (i = 0; i < src->size; i++) {

		//	Copy the cost matrix and link the two nodes.
		for(j = 0; j < src->size; j++) {
			dest->costs[i][j] = src->costs[i][j];

			if (dest->nodes[j].id == src->edges[i].start->id)
				dest->edges[i].start = &dest->nodes[j];
			if (dest->nodes[j].id == src->edges[i].end->id)
				dest->edges[i].end = &dest->nodes[j];
		}

		//	Find the previous and next edge indices.
		int nextIdx, prevIdx;
		for(j = 0; j < src->size; j++) {
			if (&dest->edges[j] == src->edges[i].next)
				nextIdx = j;
			if (&dest->edges[j] == src->edges[i].prev)
				prevIdx = j;
		}

		//	Copy the edge cost, the previous and next pointers.
		dest->edges[i].cost = src->edges[i].cost;
		dest->edges[i].next = &dest->edges[nextIdx];
		dest->edges[i].prev = &dest->edges[prevIdx];

	}
	return SUCCESS;
}
